package com.longge;

public class MaxPathSum {

    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        onSideMax(root);
        return res;

    }

    private int onSideMax(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, onSideMax(root.left));
        int right = Math.max(0, onSideMax(root.right));
        res = Math.max(res, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}
